package _2022.hot100._322_零钱兑换;

/**
 * @author： YHSimon
 * @date： 2022-05-29 09:58
 */
// 记忆化搜索 自上而下
public class Solution2 {
    public int coinChange(int[] coins,int amount){
        if(amount<1){
            return 0;
        }
        return coinChange(coins,amount,new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {
        if(rem<0){
            return -1;
        }
        if(rem==0){
            return 0;
        }
        if(count[rem-1]!=0){
            return count[rem-1];
        }
        int min=Integer.MAX_VALUE;
        for(int coin:coins){
            int res=coinChange(coins, rem-coin, count);
            if(res>=0&&res<min){
                min=1+res;
            }
        }
        count[rem-1]=(min==Integer.MAX_VALUE)?-1:min;
        return count[rem-1];
    }
}
